Microprocessor systems employing multiple processors and a combination of local and shared memory are becoming increasingly common. Such systems normally have wide interconnect busses carrying data and control information from one subsystem to another. Such systems generally have bus arbitration and access issues in accessing multiple-port memory. Busses are generally controlled by the specific processor module sending information to other modules. A classical challenge in such systems is bus arbitration that resolves collisions between separate modules striving for control of the bus.
In most DSP applications multiple port memory accesses are needed for high performance and high data bandwidth. Generally, simultaneous accesses of all ports are allowed for a wide range of applications and task synchronizations. But when multiple ports request accesses to the same memory bank, an arbiter resolves the memory conflict by enabling one request but stalling the others. Because multi-ported memory accesses may generate random conflicts among the ports in any given cycle, every port has an equal opportunity to conflict with every other port.
Fixed priority arbitration is easiest to comprehend. Table 1 shows an example of a four-port memory with fixed port priorities.
TABLE 1Port NumberPriority Value03122130A lower priority port will be able to access the memory only if its access request does not conflict with a higher priority port. This is completely unfair because port 0 will never be stalled while port 3 will always be stalled should a conflict situation arise. Arbitration should assure some degree of fairness.
Consider three classic possible solutions: iterative arbiter; oblivious arbiter; and round-robin arbiter. An iterative arbiter operates by changing the priority assignments on completion of each cycle. An oblivious arbiter does not consider the history of requests and access. The priority assignments can be generated with shift registers that rotate by one position each cycle or by decoding the output of a random number generator. Oblivious arbiters thus apply weak fairness protocols because they do not take the stall histories and current requests into account. If the same set of ports continuously conflict in synchronism with the shift register cycles, one of the ports will always win. Implementation of the random number generator is complex and costly. A round-robin arbiter achieves a higher degree of fairness by assigning the lowest priority value to the requesting port just served. Priority index numbers tend to be reduced faster than they are increased because of the random number of conflicts on different ports. When the priority index number reaches the minimum, it does not reduce further but stays fixed until a stall happens to resume normal behavior. When the priority number hits the top and bottom limits and no longer shows an accurate priority value, the arbitration mechanism ceases to behave fairly.
FIG. 1 illustrates a simplified example of a prior art four-processor system. Arbitration unit 118 determines access to shared memory 100. Four processors 111 through 114 share access to shared memory 100. Paths 105 through 108 establish communication of requests and priorities between each processor and arbitration unit 118. Arbitration unit 118 passes access decisions via a two-bit selection signal 109 to a control input of multiplexer 110. Paths 101 through 104 provide write data paths from respective processors 111 through 114 to multiplexer 110. Read return data passes from shared memory 100 to processors 111 through 114 via path 116. Arbitration unit 118 determines which processor receives the return data via control inputs 105 through 108.